#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *createNode(int data) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

TreeNode *insertNode(TreeNode *root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (root->data > data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

TreeNode *minValueNode(TreeNode *root) {
    TreeNode *current = root;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

TreeNode *deleteNode(TreeNode *root, int data) {
    if (root == NULL) {
        return root;
    }
    if (root->data > data) {
        root->left = deleteNode(root->left, data);
    } else if (root->data < data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        TreeNode *temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

TreeNode *searchNode(TreeNode *root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (root->data > data) {
        return searchNode(root->left, data);
    } else {
        return searchNode(root->right, data);
    }
}

void preOrderTraverse(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrderTraverse(root->left);
        preOrderTraverse(root->right);
    }
}

void inOrderTraverse(TreeNode *root) {
    if (root != NULL) {
        inOrderTraverse(root->left);
        printf("%d ", root->data);
        inOrderTraverse(root->right);
    }
}

void postOrderTraverse(TreeNode *root) {
    if (root != NULL) {
        postOrderTraverse(root->left);
        postOrderTraverse(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    TreeNode *root = NULL;
    root = insertNode(root, 6);
    root = insertNode(root, 1);
    root = insertNode(root, 7);
    root = insertNode(root, 2);
    root = insertNode(root, 8);
    root = insertNode(root, 3);
    root = insertNode(root, 9);
    root = deleteNode(root, 3);
    TreeNode *node = searchNode(root, 8);
    printf("%d\n", node->data);
    printf("中序遍历：");
    inOrderTraverse(root);
    printf("\n");
    printf("先序遍历：");
    preOrderTraverse(root);
    printf("\n");
    printf("后序遍历：");
    postOrderTraverse(root);
    printf("\n");
}